package com.shuang.hash8;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSum {

    public List<List<Integer>> fourSum(int[] nums, int target) {
        //双指针法 与三数之和类似 四数之和两层for循环

        //排序数组（升序）
        Arrays.sort(nums);

        //结果集
        List<List<Integer>> res = new ArrayList<>();
        //第一层循环
        for (int i = 0; i < nums.length; i++){
            //如果第一个数大于目标值后续的数还大于零则直接返回即可
            if (nums[i] > target && nums[i] >= 0){
                return res;
            }

            //对第一个数去重处理
            if (i > 0 && nums[i] == nums[i - 1]){
                continue;
            }

            //第二层循环
            for (int j = i + 1; j < nums.length; j++){
                //如果前两个数相加大于目标值 并且后续值都大于零直接跳出本次循环回到第一层循环即可
                if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0){
                    break; //跳回到第一个for循环
                }

                //定义左右指针
                int left = j + 1;
                int right = nums.length - 1;

                //对第二个数去重
                if (j > i + 1 && nums[j] == nums[j - 1]){
                    continue;
                }

                //判断四个数的和
                int sum = 0;
                while (left < right){
                    sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target){
                        right--;
                    }else if (sum < target){
                        left++;
                    }else {
                        //四个数之和等于目标值 将四个值存到结果集中去
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));

                        //对后两个数进行去重
                        while (left < right && nums[left] == nums[left + 1]){
                            left++;
                        }
                        while (left < right && nums[right] == nums[right - 1]){
                            right--;
                        }

                        //左右指针分别移动
                        left++;
                        right--;
                    }
                }
            }
        }

        //返回结果集
        return res;
    }
}
